//
// Created by ASUS on 2023/12/17.
//
#include <bits/stdc++.h>
using namespace std;

vector<int> pal;
auto init = [] {
	// 严格按顺序从小到大生成所有回文数（不用字符串转换）
	for (int base = 1; base <= 10000; base *= 10) {
		// 生成奇数长度回文数
		for (int i = base; i < base * 10; i++) {
			int x = i;
			for (int t = i / 10; t; t /= 10) {
				x = x * 10 + t % 10;
			}
			pal.push_back(x);
		}
		// 生成偶数长度回文数
		if (base <= 1000) {
			for (int i = base; i < base * 10; i++) {
				int x = i;
				for (int t = i; t; t /= 10) {
					x = x * 10 + t % 10;
				}
				pal.push_back(x);
			}
		}
	}
	pal.push_back(1'000'000'001); // 哨兵，防止下面代码中的 i 下标越界
	return 0;
}();